#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-12-08 8:49 上午
# @Author  : yangdy
# @File    : 2020-12-08.842.将数组拆分成斐波那契序列
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        # ans = [0, 0]
        # for i in range(len(S)-1):
        #     for j in range(i+1, len(S)-1):
        #         if i >= 1 and S[0] == '0' or j-i > 1 and S[i+1] == '0':
        #             break
        #         ans[0] = int(S[:i+1])
        #         ans[1] = int(S[i+1:j+1])
        #         if ans[0] + ans[1] > int(S[j+1:]):
        #             break
        #
        #         def dfs(s):
        #             if not s:
        #                 return True
        #             e = 0
        #             for ii in range(len(s)):
        #                 if ii > 0 and e == 0:
        #                     break
        #                 e = e * 10 + int(s[ii])
        #                 print(e, 1 << 32 - 1)
        #                 if e > 1 << 32 - 1:
        #                     print('break')
        #                     break
        #                 if ans[-2] + ans[-1] == e:
        #                     ans.append(e)
        #                     if dfs(s[ii+1:]):
        #                         return True
        #                     ans.pop()
        #             return False
        #
        #         if dfs(S[j+1:]):
        #             return ans
        #
        # return []
        ans = []

        def dfs(ss):
            if not ss:
                return True
            e = 0
            for i in range(len(ss)):
                if i > 0 and e == 0:
                    break
                e = e * 10 + ord(ss[i]) - ord('0')
                if e > 1 << 32 - 1:
                    return False
                if len(ans) < 2 or e == ans[-2] + ans[-1]:
                    if ss[i+1:] and len(ans) > 0 and ans[-1] + e > int(ss[i+1:]):
                        return False
                    ans.append(e)
                    if dfs(ss[i+1:]):
                        return True
                    ans.pop()
                elif e > ans[-2] + ans[-1]:
                    return False
            return False

        return ans if dfs(S) and len(ans) > 2 else []


questions = [
    ('123456579',),
    ('11235813',),
    ('112358130',),
    ('0123',),
    ("36115373839853435918344412703521047933751454799388550714335002319007375250760715149824021158955352571955641615091"
     "67334647108949738176284385285234123461518508746752631120827113919550237703163294909",),
]

work(questions, lambda q: Solution().splitIntoFibonacci(q[0]))
